﻿// 1000. 合并石头的最低成本.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>

using namespace std;
/*
https://leetcode.cn/problems/minimum-cost-to-merge-stones/
有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
每次 移动 需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数。
返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1 。

示例 1：
输入：stones = [3,2,4,1], K = 2
输出：20
解释：
从 [3, 2, 4, 1] 开始。
合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。
合并 [4, 1]，成本为 5，剩下 [5, 5]。
合并 [5, 5]，成本为 10，剩下 [10]。
总成本 20，这是可能的最小值。

示例 2：
输入：stones = [3,2,4,1], K = 3
输出：-1
解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。

示例 3：
输入：stones = [3,5,1,2,6], K = 3
输出：25
解释：
从 [3, 5, 1, 2, 6] 开始。
合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。
合并 [3, 8, 6]，成本为 17，剩下 [17]。
总成本 25，这是可能的最小值。


提示：
n == stones.length
1 <= n <= 30
1 <= stones[i] <= 100
2 <= k <= 30

*/


//class Solution {
//public:
//    int dp[50][50][50];
//    int presum[50];
//    int mergeStones(vector<int>& stones, int k) {
//        memset(dp, 0x3f, sizeof dp);
//        stones.insert(stones.begin(), 0);
//        int n = stones.size() - 1;
//
//
//        memset(presum, 0, sizeof presum);
//        memset(dp, 0x3f, sizeof dp);
//
//        for (int i = 1; i <= n; i++) {
//            presum[i] = presum[i - 1] + stones[i];
//        }
//
//        for (int i = 0; i <= n; i++) {
//            dp[i][i][1] = 0;
//        }
//
//        for (int len = 2; len <= n; len++) {
//            for (int i = 1; i + len - 1 <= n; i++) {
//                int j = i + len - 1;
//                for (int u = i; u < j; u++) {
//                    for (int z = 2; z <= k; z++) {
//                        dp[i][j][z] = min(dp[i][j][z], dp[i][u][1] + dp[u + 1][j][z - 1]);
//                    }
//                }
//
//                dp[i][j][1] = dp[i][j][k] + presum[j] - presum[i - 1];
//            }
//        }
//
//        if (dp[1][n][1] >= 0x3f3f3f3f) return -1;
//        return dp[1][n][1];
//    }
//};

class Solution {
public:
    int dp[50][50];
    int presum[50];
    int mergeStones(vector<int>& stones, int k) {
        memset(dp, 0x3f, sizeof dp);
        memset(presum, 0, sizeof presum);
        stones.insert(stones.begin(), 0);
        int n = stones.size() - 1;
        if ((n - 1) % (k - 1) != 0) return -1;
        for (int i = 0; i <= n; i++) {
            dp[i][i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            presum[i] = presum[i - 1] + stones[i];
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                for (int u = i; u < j; u+= (k-1)) {
                    dp[i][j] = min(dp[i][j], dp[i][u] + dp[u + 1][j]);
                }

                if ((len - 1) % (k - 1) == 0) {
                    dp[i][j] = dp[i][j] + presum[j] - presum[i - 1];
                }
            }
        }

        if (dp[1][n] == 0x3f3f3f3f) return -1;
        return dp[1][n];
    }
};


int main()
{
    Solution s;
    vector<int> v{ 3,5,1,2,6 };
    cout << s.mergeStones(v,3);

	return 0;
}

 